package org.wuxinshui.boosters.nowcoder.classicQuestion;

/**
 * 描述:在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
 * 示例1
 * 输入：{30,20,40}
 * 返回值：{20,30,40}
 */
public class CC4SortList_Practice {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 获取链表长度
        int length = getLength(head);

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 从大小为1开始，每次翻倍
        for (int size = 1; size < length; size *= 2) {
            ListNode prev = dummy;
            ListNode curr = dummy.next;

            while (curr != null) {
                // 获取第一个子链表
                ListNode left = curr;
                ListNode right = split(left, size);
                curr = split(right, size);

                // 合并两个有序链表
                ListNode merged = merge(left, right);
                prev.next = merged;

                // 移动prev到合并后链表的末尾
                while (prev.next != null) {
                    prev = prev.next;
                }
            }
        }

        return dummy.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // 获取链表长度
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // 分割链表，返回后半部分的头节点
    private ListNode split(ListNode head, int size) {
        if (head == null) return null;

        // 移动到第size个节点
        for (int i = 1; i < size && head.next != null; i++) {
            head = head.next;
        }

        ListNode right = head.next;
        head.next = null; // 断开连接
        return right;
    }

    // 合并两个有序链表
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        // 连接剩余部分
        if (l1 != null) {
            curr.next = l1;
        } else {
            curr.next = l2;
        }

        return dummy.next;
    }

    // 测试代码
    public static void main(String[] args) {
        CC4SortList_Practice sorter = new CC4SortList_Practice();

        // 创建测试链表: 4->2->1->3
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        System.out.println("原始链表:");
        printList(head);

        ListNode sorted = sorter.sortList(head);

        System.out.println("排序后链表:");
        printList(sorted);
    }

    // 打印链表
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) {
                System.out.print("->");
            }
            head = head.next;
        }
        System.out.println();
    }
}
